package com.niuke.asm.sort;

import java.util.Scanner;

/**
 * 描述
 * 给定一个长度为 nn 的整数数组 AA（允许元素重复），请将其按非递减顺序排序并输出。
 * 输入描述：
 * 第一行输入整数 n(1≦n≦105)n(1≦n≦105)，表示数组长度。
 * 第二行输入 nn 个整数 a1,a2,…,an(−109≦ai≦109)。
 * 输出描述：
 * 在一行上输出排序后的数组，各元素以空格分隔。
 */
public class SortTest01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 待排序的数组的长度
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        //开始排序，使用快速排序
        quickSort(nums, 0, n - 1);
        //输出排序后的数组
        printRes(nums);
    }
    // 快速排序的方法
    private static void quickSort(int[] nums, int low, int high) {
        //递归终止条件
        if(low < high){
            //获得基准元素
            int partion = partitions(nums, low, high);
            //排序基准元素之前的元素
            quickSort(nums, low, partion - 1);
            //排序基准元素之后的元素
            quickSort(nums, partion + 1, high);
        }
    }
    //寻找基准元素
    private static int partitions(int[] nums, int low, int high) {
        //选择一个元素作为基准
        int pivot = nums[high];
        int i = low - 1;
        //遍历数组，将小于基准的元素放到左边区域
        for (int j = low; j <high ; j++) {
            //如果当前元素小于或者等于基准元素
            if(nums[j] < pivot){
                i ++;
                //交换nums[i]和nums[j]
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        // 将基准元素放到正确地方
        int temp = nums[i+1];
        nums[i+1] = nums[high];
        nums[high] = temp;
        return i + 1;
    }

    //打印排序后的数组
    private static void printRes(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}
